<!DOCTYPE html>
<html lang="zh-cmn-Hans">
<head>
  <meta charset="UTF-8">
  <meta name="viewport" content="width=device-width, initial-scale=1.0">
  <meta http-equiv="X-UA-Compatible" content="ie=edge">
  <title>09-数据抽象 | hez2010</title>
  
  
  
  <!--link rel="stylesheet" href="//cdn.jsdelivr.net/highlight.js/9.10.0/styles/github-gist.min.css"-->
  
<link rel="stylesheet" href="//cdn.jsdelivr.net/highlight.js/9.10.0/styles/github-gist.min.css">

  
<link rel="stylesheet" href="/css/style.css">

<!-- hexo injector head_end start -->
<link rel="stylesheet" href="https://cdn.jsdelivr.net/npm/katex@0.12.0/dist/katex.min.css">

<link rel="stylesheet" href="https://cdn.jsdelivr.net/npm/hexo-math@4.0.0/dist/style.css">
<!-- hexo injector head_end end --><meta name="generator" content="Hexo 5.1.1"></head>

<body>
<div class="Shell">
    <aside class='SideBar'>
    <section class='avatar' style="background-image: url()">
        <div class='av-pic' style="background-image: url(/assets/avatar.jpg)">
        </div>
    </section>
    <section class='menu'>
        <div>hez2010</div>
        
            <div>软件工程导论</div>
        
        <ul>
          
            <a href="/" class="Btn">
              <li>Home</li>
            </a>  
          
            <a href="/archives/" class="Btn">
              <li>Archive</li>
            </a>  
          
        </ul>
    </section>
    <section class="media">
        
            
                <a target="_blank" rel="noopener" href="https://github.com/hez2010">
                    <img src="/assets/github.svg" />
                </a>
            
        
    </section>
</aside>

    <div class="container">
        <div data-pager-shell>
            <div>
  <article class='ContentView'>
    <header class='PageTitle'>
        <h1>09-数据抽象</h1>
    </header>

    <section>
      <h1 id="Homework-9"><a href="#Homework-9" class="headerlink" title="Homework 9"></a>Homework 9</h1><h2 id="Bubble-Sort-the-list-33-56-17-8-95-22。"><a href="#Bubble-Sort-the-list-33-56-17-8-95-22。" class="headerlink" title="Bubble Sort the list: 33, 56, 17, 8, 95, 22。"></a>Bubble Sort the list: 33, 56, 17, 8, 95, 22。</h2><p>Make sure the final result is from small to large.</p>
<p>Write out the list after the 2nd pass.</p>
<p>第一趟结果：8, 33, 56, 17, 22, 95 </p>
<p>第二趟结果：8, 17, 33, 56, 22, 95 </p>
<h2 id="Give-a-sorted-array-as-list-60-65-75-80-90-95-Design-an-algorithm-to-insert-the-value-of-x-into-the-sorted-array-Then-test-the-algorithm-with-value-50-67-99"><a href="#Give-a-sorted-array-as-list-60-65-75-80-90-95-Design-an-algorithm-to-insert-the-value-of-x-into-the-sorted-array-Then-test-the-algorithm-with-value-50-67-99" class="headerlink" title="Give a sorted array as list={60,65,75,80,90,95}. Design an algorithm to insert the value of x into the sorted array. Then test the algorithm with value 50,67,99."></a>Give a sorted array as list={60,65,75,80,90,95}. Design an algorithm to insert the value of x into the sorted array. Then test the algorithm with value 50,67,99.</h2><p>使用二分查找算法找到合适的位置进行插入。</p>
<figure class="highlight cpp"><table><tr><td class="gutter"><pre><span class="line">1</span><br><span class="line">2</span><br><span class="line">3</span><br><span class="line">4</span><br><span class="line">5</span><br><span class="line">6</span><br><span class="line">7</span><br><span class="line">8</span><br><span class="line">9</span><br><span class="line">10</span><br><span class="line">11</span><br><span class="line">12</span><br><span class="line">13</span><br><span class="line">14</span><br><span class="line">15</span><br><span class="line">16</span><br><span class="line">17</span><br><span class="line">18</span><br><span class="line">19</span><br><span class="line">20</span><br><span class="line">21</span><br><span class="line">22</span><br><span class="line">23</span><br><span class="line">24</span><br><span class="line">25</span><br><span class="line">26</span><br><span class="line">27</span><br><span class="line">28</span><br><span class="line">29</span><br><span class="line">30</span><br><span class="line">31</span><br><span class="line">32</span><br><span class="line">33</span><br><span class="line">34</span><br></pre></td><td class="code"><pre><code class="hljs cpp"><span class="hljs-meta">#<span class="hljs-meta-keyword">include</span> <span class="hljs-meta-string">&lt;vector&gt;</span></span><br><span class="hljs-meta">#<span class="hljs-meta-keyword">include</span> <span class="hljs-meta-string">&lt;iostream&gt;</span></span><br><br><span class="hljs-built_in">std</span>::<span class="hljs-built_in">vector</span>&lt;<span class="hljs-keyword">int</span>&gt; <span class="hljs-built_in">list</span> = &#123;<span class="hljs-number">60</span>,<span class="hljs-number">65</span>,<span class="hljs-number">75</span>,<span class="hljs-number">80</span>,<span class="hljs-number">90</span>,<span class="hljs-number">95</span>&#125;;<br><br><span class="hljs-function"><span class="hljs-keyword">void</span> <span class="hljs-title">print</span><span class="hljs-params">()</span> </span>&#123;<br>    <span class="hljs-keyword">for</span> (<span class="hljs-keyword">auto</span> &amp;i : <span class="hljs-built_in">list</span>) &#123;<br>        <span class="hljs-built_in">std</span>::<span class="hljs-built_in">cout</span> &lt;&lt; i &lt;&lt; <span class="hljs-string">&quot; &quot;</span>;<br>    &#125;<br>    <span class="hljs-built_in">std</span>::<span class="hljs-built_in">cout</span> &lt;&lt; <span class="hljs-built_in">std</span>::<span class="hljs-built_in">endl</span>;<br>&#125;<br><br><span class="hljs-function"><span class="hljs-keyword">void</span> <span class="hljs-title">insert</span><span class="hljs-params">(<span class="hljs-keyword">int</span> l, <span class="hljs-keyword">int</span> r, <span class="hljs-keyword">int</span> value)</span> </span>&#123;<br>    <span class="hljs-keyword">if</span> (l == r) &#123;<br>      <span class="hljs-built_in">list</span>.insert(<span class="hljs-built_in">list</span>.begin() + l + (<span class="hljs-built_in">list</span>[l] &gt;= value ? <span class="hljs-number">0</span> : <span class="hljs-number">1</span>), value);<br>      <span class="hljs-keyword">return</span>;<br>    &#125;<br>    <span class="hljs-keyword">int</span> mid = (l + r) / <span class="hljs-number">2</span>;<br>    <span class="hljs-keyword">if</span> (<span class="hljs-built_in">list</span>[mid] &lt; value) &#123;<br>        insert(mid + <span class="hljs-number">1</span>, r, value);<br>    &#125;<br>    <span class="hljs-keyword">else</span> &#123;<br>        insert(l, mid, value);<br>    &#125;<br>&#125;<br><br><span class="hljs-function"><span class="hljs-keyword">int</span> <span class="hljs-title">main</span><span class="hljs-params">()</span> </span>&#123;<br>    insert(<span class="hljs-number">0</span>, <span class="hljs-built_in">list</span>.size() - <span class="hljs-number">1</span>, <span class="hljs-number">50</span>);<br>    print();<br>    insert(<span class="hljs-number">0</span>, <span class="hljs-built_in">list</span>.size() - <span class="hljs-number">1</span>, <span class="hljs-number">67</span>);<br>    print();<br>    insert(<span class="hljs-number">0</span>, <span class="hljs-built_in">list</span>.size() - <span class="hljs-number">1</span>, <span class="hljs-number">99</span>);<br>    print();<br>&#125;<br></code></pre></td></tr></table></figure>

<p>输出：</p>
<figure class="highlight plain"><table><tr><td class="gutter"><pre><span class="line">1</span><br><span class="line">2</span><br><span class="line">3</span><br></pre></td><td class="code"><pre><code class="hljs none">50 60 65 75 80 90 95 <br>50 60 65 67 75 80 90 95 <br>50 60 65 67 75 80 90 95 99 <br></code></pre></td></tr></table></figure>

<h3 id="思考：为什么选择插入点在list头上、中间、尾巴上的三个数作为算法测试的数据，你能解释吗？"><a href="#思考：为什么选择插入点在list头上、中间、尾巴上的三个数作为算法测试的数据，你能解释吗？" class="headerlink" title="思考：为什么选择插入点在list头上、中间、尾巴上的三个数作为算法测试的数据，你能解释吗？"></a>思考：为什么选择插入点在list头上、中间、尾巴上的三个数作为算法测试的数据，你能解释吗？</h3><p>因为在中间的时候需要判断定位到的位置下原来的数和待插入的数的大小关系，在头上的时候需要插入到最前面，而在尾巴上则需要插入到最后面，较容易出错。</p>
<h2 id="What-is-the-state-of-the-stack-after-the-following-sequence-of-Push-and-Pop-operations"><a href="#What-is-the-state-of-the-stack-after-the-following-sequence-of-Push-and-Pop-operations" class="headerlink" title="What is the state of the stack after the following sequence of Push and Pop operations?"></a>What is the state of the stack after the following sequence of Push and Pop operations?</h2><p>Push “anne”; Push “get”; Push “your” ; Pop; Push “my” Push “gun”</p>
<p>栈的变化如下：</p>
<figure class="highlight plain"><table><tr><td class="gutter"><pre><span class="line">1</span><br><span class="line">2</span><br><span class="line">3</span><br><span class="line">4</span><br><span class="line">5</span><br><span class="line">6</span><br></pre></td><td class="code"><pre><code class="hljs none">anne<br>get anne<br>your get anne<br>get anne<br>my get anne<br>gun my get anne<br></code></pre></td></tr></table></figure>

<p>所以最后结果是：</p>
<figure class="highlight plain"><table><tr><td class="gutter"><pre><span class="line">1</span><br></pre></td><td class="code"><pre><code class="hljs none">gun my get anne<br></code></pre></td></tr></table></figure>


      

    </section>
    
      <section class='ArticleMeta'>
          <div>
            发布于&nbsp;
            <time datetime="2020-11-11T14:54:11.325Z" itemprop="datePublished">
              2020-11-11
            </time>
          </div>
          
      </section>
    
    
</article>

  
</div>

            <footer>
    <div>© 2021 - Steven He </div>
    <div>
        <span>
            Powered by <a target="_blank" rel="noopener" href="https://hexo.io">Hexo</a>
        </span>
        ,
        <span>
            Theme - <a target="_blank" rel="noopener" href="https://github.com/nameoverflow/hexo-theme-icalm">Icalm</a>
        </span>
    </div>
</footer>

        </div>
    </div>
</div>

<script src="/js/pager/dist/singlepager.js"></script>

<script>
var sp = new Pager('data-pager-shell')

</script>
</body>
</html>